package com.game.astar{
	public class Astar {
		private static var isPathFind:Boolean;
		private static var closeA:Array;
		private static var findA:Array;
		private static var dirA:Array=[[1,0,10],[0,1,10],[-1,0,10],[0,-1,10],[1,1,14],[-1,1,14],[-1,-1,14],[1,-1,14]];
		private static var openA:Array;
		private static var walkA:Array;
		private static var endX:int;
		private static var endY:int;
		
		private static var _ex:int;
		private static var _ey:int;
		private static var _sy:int;
		private static var _sx:int;
		
		private static var maxTry : int = 20000;
		
		private static var _mapArr:MapFloor;
		
		private static var affectList:Array;
		private static var beAffectedList:Array;
		
		private static var StepLength:int = 20;
		
		public static function getOpenArr():Array
		{
			return openA;
		}
		
		public static function getCloseArr():Array
		{
			return closeA;
		}
		
		public static function startSearch(sx:int, sy:int, ex:int,ey:int, mapArr:MapFloor):Array {
			affectList = [];
			beAffectedList = [];
			
			i = 0;
			_mapArr = mapArr;
			_ex = ex;
			_ey = ey;
			_sx = sx;
			_sy = sy;
			
			
			var emptyArray:Array;
			endX=ex/StepLength;
			endY=ey/StepLength;
			isPathFind=false;
			findA=new Array();
			openA=new Array();
			closeA=new Array();
			searchPath(sx/StepLength,sy/StepLength,sx/StepLength,sy/StepLength,0);
			if (isPathFind) {
				return getPath();
			}
			return emptyArray;
		}
		
		private static function getPath():Array {
			var i:int=closeA.length - 1;
			var n:int=0;
			walkA =	[];
			walkA.push([_ex, _ey]);
			walkA.push([closeA[i][0] * StepLength, closeA[i][1] * StepLength]);
			var px:int=closeA[i][2];
			var py:int=closeA[i][3];
			for (var j:int=i - 1; j >= 0; j--) {
				if (px == closeA[j][0] && py == closeA[j][1]) {
					n++;
					walkA[n]=[closeA[j][0] * StepLength, closeA[j][1] * StepLength];
					px=closeA[j][2];
					py=closeA[j][3];
				}
			}
			walkA.push([_sx, _sy]);
			walkA.reverse();
			return walkA;
		}
		
		private  static var i:int;
		private  static function searchPath(nx:int,ny:int,px:int,py:int,g:int):void {
			while(true)
			{
				i ++;
				
				if(maxTry < i)
				{
					isPathFind=false;
					return;
				}
				var hval:int=0;
				var gval:int=0;
				var min:int=0;
				var len:int=0;
				findA[ny] = findA[ny]||[]
				findA[ny][nx]=[1];
				closeA.push([nx,ny,px,py]);
				for (var n:int=0; n < 8; n++) {
					var adjX:int = nx + dirA[n][0];
					var adjY:int = ny + dirA[n][1];
					if (adjX < 0 || adjX >= int(_mapArr.mapWidth/StepLength) || adjY < 0 || adjY >= int(_mapArr.mapHeight/StepLength)) {
						continue;
					}
					if (adjX == endX && adjY == endY) {
						closeA.push([adjX,adjY,nx,ny]);
						isPathFind=true;
						return;
					}
					if (!_mapArr.isWall(adjX*StepLength, adjY*StepLength)) {
						if (findA[adjY] && findA[adjY][adjX]) {
							gval=g + dirA[n][2];
							if (gval < findA[adjY][adjX][0]) {
								var difference:int = gval - findA[adjY][adjX][0];
								findA[adjY][adjX][0] += difference;
								findA[adjY][adjX][1][4] += difference;
								findA[adjY][adjX][1][5] += difference;
								for each(var key:String in affectList[adjY+adjX*10000])
								{
									if(beAffectedList[key] == adjY+adjX*10000)
									{
										findA[int(key)%10000][int(int(key)/10000)][0] += difference;
										findA[int(key)%10000][int(int(key)/10000)][1][4] += difference;
										findA[int(key)%10000][int(int(key)/10000)][1][5] += difference;
									}
								}
								
								affectList[ny+nx*10000] = affectList[ny+nx*10000] || [];
								affectList[ny+nx*10000].push(adjY+adjX*10000);
								beAffectedList[adjY+adjX*10000] = ny+nx*10000;
							}
						}else{
							hval= 10 * (Math.abs(endX - adjX) + Math.abs(endY - adjY));
							gval=g + dirA[n][2];
							findA[adjY] = findA[adjY]||[]
							findA[adjY][adjX]=[gval,[adjX,adjY,nx,ny,gval + hval,gval]];
							openA.push(findA[adjY][adjX][1]);
							
							affectList[ny+nx*10000] = affectList[ny+nx*10000] || [];
							affectList[ny+nx*10000].push(adjY+adjX*10000);
							beAffectedList[adjY+adjX*10000] = ny+nx*10000;
						}
					} 
				}
				if (openA.length < 1) {
					//trace("No Path");
					isPathFind=false;
					return;
				} else {
					len=openA.length;
					for (var m:int=0; m < len; m++) {
						if (openA[min][4] > openA[m][4]) {
							min=m;//获取最小F值
						}
					}
					var moveToCloseA:Array=openA.splice(min,1);
					nx = moveToCloseA[0][0];
					ny = moveToCloseA[0][1];
					px = moveToCloseA[0][2];
					py = moveToCloseA[0][3];
					g = moveToCloseA[0][5];
				}
			}
		}
	}
}